#include <iostream>
#include <map>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
		val(x), left(NULL), right(NULL) {
	}
};

TreeNode* Convert(TreeNode* pRootOfTree)
{
	if (pRootOfTree == NULL)
		return NULL;

	TreeNode *leftHead = Convert(pRootOfTree->left), *rightHead = Convert(pRootOfTree->right);
	if (leftHead == NULL && rightHead == NULL)
	{
		pRootOfTree->left = pRootOfTree->right = NULL;
		return pRootOfTree;
	}
	else if (leftHead != NULL)
	{
		TreeNode *llast = leftHead;
		while (llast->right != NULL)
			llast = llast->right;
		pRootOfTree->left = llast;
		llast->right = pRootOfTree;
		if (rightHead != NULL)
		{
			pRootOfTree->right = rightHead;
			rightHead->left = pRootOfTree;
			return leftHead;
		}
		else
		{
			pRootOfTree->right = NULL;
			return leftHead;
		}
	}
	else
	{
		rightHead->left = pRootOfTree;
		pRootOfTree->left = NULL;
		pRootOfTree->right = rightHead;
		return pRootOfTree;
	}
}

//cycle tree
TreeNode* Convert2(TreeNode* pRootOfTree)
{
	if (pRootOfTree == NULL)
		return NULL;

	TreeNode *leftHead = Convert(pRootOfTree->left), *rightHead = Convert(pRootOfTree->right);
	if (leftHead == NULL && rightHead == NULL)
	{
		pRootOfTree->left = pRootOfTree->right = pRootOfTree;
		return pRootOfTree;
	}
	else if (leftHead != NULL)
	{
		pRootOfTree->left = leftHead->left;
		leftHead->left->right = pRootOfTree;
		if (rightHead != NULL)
		{
			pRootOfTree->right = rightHead;
			leftHead->left = rightHead->left;
			rightHead->left->right = leftHead;
			rightHead->left = pRootOfTree;
			return leftHead;
		}
		else
		{
			pRootOfTree->right = leftHead;
			leftHead->left = pRootOfTree;
			return leftHead;
		}
	}
	else
	{
		rightHead->left->right = pRootOfTree;
		pRootOfTree->left = rightHead->left;
		rightHead->left = pRootOfTree;
		pRootOfTree->right = rightHead;
		return pRootOfTree;
	}
}

//int main()
//{
//	TreeNode *root = new TreeNode(5);
//	TreeNode *p1 = new TreeNode(1);
//	TreeNode *p2 = new TreeNode(2);
//	TreeNode *p3 = new TreeNode(3);
//	TreeNode *p6 = new TreeNode(6);
//	TreeNode *p7 = new TreeNode(7);
//	TreeNode *p8 = new TreeNode(8);
//
//	//root->left = p2;
//	//root->right = p7;
//	////p2->left = p1;
//	//p2->right = p3;
//	//p7->left = p6;
//	//p7->right = p8;
//
//	TreeNode *newHead = Convert(root);
//	system("pause");
//	return 0;
//}